{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# `std::vector` 扩容复杂度与异常安全\n",
    "\n",
    "- **扩容触发**：插入导致容量不足时，通常按 2× 或实现定义的倍数增长。\n",
    "- **复杂度**：摊销 O(1)。一次扩容需分配新内存并移动/拷贝所有元素，复杂度 O(n)，但由于扩容频率指数下降，均摊后单次 `push_back` 仍是常数摊销。\n",
    "- **异常安全**：扩容会分配新内存并逐个构造新元素；若过程中抛异常：\n",
    "  - 已成功搬迁的元素会销毁，新内存释放；\n",
    "  - 原 vector 保持原状（强异常保证），前提是移动/拷贝构造满足至少基本异常安全。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `std::vector<bool>`\n",
    "\n",
    "特化为 bit-pack，节省空间。迭代器不是普通指针，而是 proxy，对应的引用类型为 `std::vector<bool>::reference`。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# `std::list` / `std::forward_list` / `std::deque` 的迭代器稳定性\n",
    "\n",
    "| 容器                | 迭代器失效条件                                               |\n",
    "| ------------------- | ------------------------------------------------------------ |\n",
    "| `std::list`         | 节点式：插入、删除不会使其他元素迭代器失效（除被删元素）。   |\n",
    "| `std::forward_list` | 同上，但为单向链表。                                         |\n",
    "| `std::deque`        | 复杂：在首尾插入可能使所有迭代器失效；中间插入/删除亦可能失效，指针/引用在重分块时不稳定。 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 自定义 `std::unordered_map` 的哈希函数与相等谓词\n",
    "\n",
    "可在模板参数指定 Hash 与 KeyEqual："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "#include <unordered_map>\n",
    "#include <string>\n",
    "#include <functional>\n",
    "\n",
    "struct MyHash {\n",
    "    std::size_t operator()(const std::string& s) const noexcept {\n",
    "        return std::hash<std::string>{}(s);\n",
    "    }\n",
    "};\n",
    "\n",
    "struct MyEq {\n",
    "    bool operator()(const std::string& a, const std::string& b) const noexcept {\n",
    "        return a.size() == b.size(); // 示例：按长度比较\n",
    "    }\n",
    "};\n",
    "\n",
    "int main() {\n",
    "    std::unordered_map<std::string, int, MyHash, MyEq> map;\n",
    "    map[\"foo\"] = 1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# `emplace` vs `insert`；`emplace_back` 退化为 `push_back` 的情况\n",
    "\n",
    "- `insert` 需要传递已构造对象，可能产生额外拷贝/移动。\n",
    "- `emplace` 接受构造参数，直接在容器内部原地构造，避免临时对象。\n",
    "- 当传入 `emplace_back(x)` 且参数是现有对象时，仍需要复制/移动以匹配构造函数，从而与 `push_back(x)` 无异；真正的优势在于传递构造参数列表。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "#include <iostream>\n",
    "#include <vector>\n",
    "#include <string>\n",
    "#include <type_traits>\n",
    "\n",
    "struct Trace {\n",
    "    std::string s;\n",
    "\n",
    "    Trace(const char* str) : s(str) { std::cout << \"Trace(const char*)\\n\"; }\n",
    "    Trace(const Trace& other) : s(other.s) { std::cout << \"Trace copy ctor\\n\"; }\n",
    "    Trace(Trace&& other) noexcept : s(std::move(other.s)) { std::cout << \"Trace move ctor\\n\"; }\n",
    "\n",
    "    Trace& operator=(const Trace&) = default;         // 允许拷贝赋值\n",
    "    Trace& operator=(Trace&&) noexcept = default;     // 或者自定义移动赋值\n",
    "};"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "== push_back(Trace(\"alpha\")) ==\n",
      "Trace(const char*)\n",
      "Trace copy ctor\n",
      "--\n",
      "\n",
      "== emplace_back(\"beta\") ==\n",
      "Trace(const char*)\n",
      "Trace move ctor\n",
      "--\n",
      "\n",
      "== emplace_back(tmp) (退化) ==\n",
      "Trace copy ctor\n",
      "Trace move ctor\n",
      "Trace move ctor\n",
      "--\n",
      "\n",
      "== insert(v.begin(), Trace(\"gamma\")) ==\n",
      "Trace(const char*)\n",
      "Trace move ctor\n",
      "--\n",
      "\n",
      "== emplace(v.begin(), \"delta\") ==\n",
      "Trace(const char*)\n",
      "Trace move ctor\n",
      "Trace move ctor\n",
      "Trace move ctor\n",
      "Trace move ctor\n",
      "--\n"
     ]
    }
   ],
   "source": [
    "{\n",
    "    std::vector<Trace> v;\n",
    "\n",
    "    std::cout << \"\\n== push_back(Trace(\\\"alpha\\\")) ==\\n\";\n",
    "    Trace tmp(\"alpha\");\n",
    "    v.push_back(tmp); // 拷贝\n",
    "    std::cout << \"--\\n\";\n",
    "\n",
    "    std::cout << \"\\n== emplace_back(\\\"beta\\\") ==\\n\";\n",
    "    v.emplace_back(\"beta\"); // emplace_back(\"beta\") 直接调用构造函数，无额外拷贝/移动。\n",
    "    std::cout << \"--\\n\";\n",
    "\n",
    "    std::cout << \"\\n== emplace_back(tmp) (退化) ==\\n\";\n",
    "    v.emplace_back(tmp); // emplace_back(tmp) 因传入现成对象，仍需拷贝 → 退化为 push_back(tmp)\n",
    "    std::cout << \"--\\n\";\n",
    "\n",
    "    std::cout << \"\\n== insert(v.begin(), Trace(\\\"gamma\\\")) ==\\n\";\n",
    "    v.insert(v.begin(), Trace(\"gamma\")); // 先构造临时，再移动到插入位置\n",
    "    std::cout << \"--\\n\";\n",
    "\n",
    "    std::cout << \"\\n== emplace(v.begin(), \\\"delta\\\") ==\\n\";\n",
    "    v.emplace(v.begin(), \"delta\"); // 在目标位置直接构造\n",
    "    std::cout << \"--\\n\";\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# `std::map` 迭代器失效\n",
    "\n",
    "- 插入不会使迭代器失效。\n",
    "- `erase(iterator)` 会使该迭代器及指向同节点的迭代器失效；返回值是下一个迭代器。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "for (auto it = m.begin(); it != m.end(); ) {\n",
    "    if (condition) it = m.erase(it);\n",
    "    else ++it;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# `std::priority_queue`\n",
    "\n",
    "- 基于 `std::vector` + `std::make_heap`/`push_heap`/`pop_heap`。\n",
    "- 自定义比较器：`std::priority_queue<T, std::vector<T>, std::greater<T>> minq;`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# `std::flat_map`（非标准） / `vector + lower_bound`\n",
    "\n",
    "- 优势：连续内存，cache 友好，适合查找远多于修改的场景。\n",
    "- 劣势：插入/删除需移动元素，O(N)。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// 模拟\n",
    "\n",
    "auto it = std::lower_bound(vec.begin(), vec.end(), key, Cmp{});\n",
    "if (it == vec.end() || it->first != key) vec.insert(it, value);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# `std::span`（C++20）及 C++17 替代\n",
    "\n",
    "- 提供非拥有的连续视图（指针+长度），避免传 `T*` + size 分离。\n",
    "- C++17 替代：`gsl::span`, `boost::span`, 或自定义简单类。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "C++17",
   "version": "17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
